76A - Gift - CodeForces Solution

#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)
#define ff     first
#define ss     second
#define pb     push_back
#define ppb    pop_back
#define pf     push_front
#define ppf    pop_front

template <typename T> using Ordered_Set_Tree =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using Ordered_Multiset_Tree =
        tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename A, typename B> ostream& operator<<(ostream& s, const pair<A, B>& self) {s << self.first << ' ' << self.second << '\n'; return s; }
template <typename A, typename B> ostream& operator<<(ostream& s, const vector<pair<A, B>>& self) { for (auto &[a, b] : self) { s << a << ' ' << b << '\n'; } return s; }
template <typename A, typename B> ostream& operator<<(ostream& s, const set<pair<A, B>>& self) { for (auto &[a, b] : self) { s << a << ' ' << b << '\n'; } return s; }
template <typename A, typename B> ostream& operator<<(ostream& s, const multiset<pair<A, B>>& self) { for (auto &[a, b] : self) { s << a << ' ' << b << '\n'; } return s; }
template <typename A, typename B, typename C> ostream& operator<<(ostream& s, tuple<A, B, C>& self) { s << get<0>(self) << ' ' << get<1>(self) << ' ' << get<2>(self); return s; }
template <typename A, typename B, typename C, typename D> ostream& operator<<(ostream& s, tuple<A, B, C, D>& self) { s << get<0>(self) << ' ' << get<1>(self) << ' ' << get<2>(self) << ' ' << get<3>(self); return s; }
template <typename T> ostream& operator<<(ostream& s, const vector<T>& self) { for (auto &e : self) { s << e << ' '; } return s; }
template <typename T> ostream& operator<<(ostream& s, const set<T>& self) { for (auto &e : self) { s << e << ' '; } return s; }
template <typename T> ostream& operator<<(ostream& s, const multiset<T>& self) { for (auto &e : self) { s << e << ' '; } return s; }
template <typename A, typename B> ostream& operator<<(ostream& s, const map<A, B>& self) { for (auto &[a, b] : self) { s << a << ' ' << b << '\n'; } return s; }
template <typename A, typename B> ostream& operator<<(ostream& s, const unordered_map<A, B>& self) { for (auto &[a, b] : self) { s << a << ' ' << b << '\n'; } return s; }
template <typename A, typename B> istream& operator>>(istream& s, pair<A, B>& self) { s >> self.first >> self.second; return s; }
template <typename A, typename B, typename C> istream& operator>>(istream& s, tuple<A, B, C>& self) { s >> get<0>(self) >> get<1>(self) >> get<2>(self); return s; }
template <typename A, typename B, typename C, typename D> istream& operator>>(istream& s, tuple<A, B, C, D>& self) { s >> get<0>(self) >> get<1>(self) >> get<2>(self) >> get<3>(self); return s; }
template <typename T> istream& operator>>(istream& s, vector<T>& self) { for (size_t i = 0; i < self.size(); ++i) { s >> self[i]; } return s; }

#ifdef ONLINE_JUDGE
#define debug
#define _Print
#else
#define debug __debug
#define _Print __Print
#endif

///DEBUG
void __Print(int t) {cerr << t;}
void __Print(string t) {cerr << t;}
void __Print(char t) {cerr << t;}
void __Print(long long t) {cerr << t;}
void __Print(double t) {cerr << t;}
void __Print(unsigned long long t) {cerr << t;}

template <class T, class V> void __Print(pair <T, V> &p);
template <class T> void __Print(list <T> &v);
template <class T> void __Print(vector <T> &v);
template <class T> void __Print(deque <T> &v);
template <class T, class V> void __Print(T *v, V sz);
template <class T, class V, class P> void __Print(T *v, V sz, P sm);
template <class T> void __Print(set <T> &v);
template <class T, class V> void __Print(map <T, V> &v);
template <class T> void __Print(multiset <T> &v);

template <class T, class V> void __Print(pair <T, V> &p) {cerr << "{"; __Print(p.ff); cerr << ","; __Print(p.ss); cerr << "}\n\n";}
template <class T> void __Print(list <T> &v) {cerr << "[ "; for (T i : v) {__Print(i); cerr << " ";} cerr << "]\n\n";}
template <class T> void __Print(vector <T> &v) {cerr << "[ "; for (T i : v) {__Print(i); cerr << " ";} cerr << "]\n\n";}
template <class T> void __Print(deque <T> &v) {cerr << "[ "; for (T i : v) {__Print(i); cerr << " ";} cerr << "]\n\n";}
template <class T, class V> void __Print(T *v, V sz) {cerr << "[ "; for(int i=0; i<sz; i++) {__Print(v[i]); cerr << " ";} cerr << "]\n\n";}
template <class T, class V, class P> void __Print(T *v, V sz, P sm) {cerr << "[\n"; for(int i=0; i<sz; i++) { for(int j=0; j<sm; j++) {__Print(v[i][j]); cerr << " ";} cerr << "\n";} cerr << "]\n\n";}
template <class T> void __Print(set <T> &v) {cerr << "[ "; for (T i : v) {__Print(i); cerr << " ";} cerr << "]\n\n";}
template <class T> void __Print(unordered_set <T> &v) {cerr << "[ "; for (T i : v) {__Print(i); cerr << " ";} cerr << "]\n\n";}
template <class T> void __Print(multiset <T>& v) {cerr << "[ "; for (T i : v) {__Print(i); cerr << " ";} cerr << "]\n\n";}
template <class T, class V> void __Print(map <T, V> &v) {cerr << "[ "; for (auto i : v) {__Print(i); cerr << " ";} cerr << "]\n\n";}
template <class T, class V> void __Print(unordered_map <T, V> &v) {cerr << "[ "; for (auto i : v) {__Print(i); cerr << " ";} cerr << "]\n\n";}

#define __debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
vector<string> vec_splitter(string s)
{
    s += ',';
    vector<string> res;
    while(!s.empty())
    {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx, __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T)
{
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
///DEBUG

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ///freopen("input.txt", "r", stdin);
    ///freopen("output.txt", "w", stdout);

    int n, m;
    cin>>n>>m;

    int G, S;
    cin>>G>>S;

    vector<array<ll int, 4>> gsuv;

    for(int i=0; i<m; i++)
    {
        ll int u, v, g, s;
        cin>>u>>v>>g>>s;

        if(u == v)      continue;

        u--, v--;

        gsuv.pb({g, s, u, v});
    }

    sort(gsuv.begin(), gsuv.end());
    vector<set<array<ll int, 2>>> graph(n);

    int tot = 0;
    ll int ans = 9e18;
    ll int val = 0;

    vector<array<ll int, 2>> prev(n);
    vector<int> vis(n);

    function<void(int)> DFS = [&](int u)
    {
        for(auto [v, w]: graph[u])
        {
            if(!vis[v])
            {
                vis[v] = 1;
                prev[v] = {u, w};
                DFS(v);
            }
        }
    };

    array<ll int, 2> tmp = {-1, 0};

    auto addEdge = [&](int u, int v, int s)
    {
        fill(vis.begin(), vis.end(), 0);
        fill(prev.begin(), prev.end(), tmp);
        DFS(u);

        if(vis[v])
        {
            ll int mmax = 0;
            int tmpu, tmpv, x=v;

            while(x != u)
            {
                if(mmax < prev[x][1])
                {
                    mmax = prev[x][1];
                    tmpu = prev[x][0];
                    tmpv = x;
                }

                x = prev[x][0];
            }

            if(mmax <= s)        return 0;

            graph[tmpu].erase({tmpv, mmax});
            graph[tmpv].erase({tmpu, mmax});

            graph[u].insert({v, s});
            graph[v].insert({u, s});

            val = 0;
            for(int i=0; i<n; i++)
            {
                for(auto [v, w]: graph[i])
                    val = max(val, w);
            }

            return 0;
        }

        val = max(val, s*1ll);
        graph[u].insert({v, s});
        graph[v].insert({u, s});

        return 1;
    };

    for(auto [g, s, u, v]: gsuv)
    {
        tot += addEdge(u, v, s);

        assert(tot <= n-1);

        if(tot == n-1)      ans = min(ans, g*G + val*S);
    }

    if(ans == 9e18)      ans = -1;

    cout<<ans<<"\n";
}